package com.heima.datastructure.priorityqueue;

import com.heima.datastructure.queue.Queue;

import java.util.Iterator;

// 一、完全二叉树：
//     1、除了最后一层之外的所有层都必须为满
//     2、最后一层可以为满也可以不为满
//     3、往完全二叉树中添加元素时必须是在最后一层靠左往右依次添加
//     4、往完全二叉树中删除元素时必须是在最后一层靠右往左依次删除
// 二、堆：
//     1、是一个种基于树的数据结构，通常用完全二叉树实现
//     2、大顶堆：大顶堆中任意一个节点C与其父节点P满足：P.value >= C.value，所以根节点就是大顶堆中value最大的节点
//     3、小顶堆：小顶堆中任意一个节点C与其父节点P满足：P.value <= C.value，所以根节点就是大顶堆中value最小的节点
//     4、若用数组来存储堆节点：
//       （1）往大顶堆中添加节点时，可能会破坏大顶堆的特性，添加后将其与父节点比较，如果P.value < C.value，则交换两个节点，继续往上比较
//       （2）往小顶堆中添加节点时，可能会破坏小顶堆的特性，添加后将其与父节点比较，如果P.value > C.value, 则交换两个节点，继续往上比较
//       （3）若想要删除大顶堆或小顶堆的根节点，则将根节点与层序遍历的最后一个节点也就是数组中最后一个元素交换，删除数组最后一个元素，并让交换到根节点的节点下潜到合理的位置
// 三、用数组存放完全二叉树：
//     1、存放方式就是对完全二叉树层序遍历依次把遍历到的节点存到数组中去
//     2、如果从索引0开始存储节点数据
//       （1）索引为i的节点的父节点为floor((i-1)/2)
//       （2）索引为i的节点的左子节点为2i + 1，右子节点为2i + 2，当然他们得 < size
//     3、如果从索引1开始存储节点数据
//       （1）索引为i的节点的父节点为floor(i/2)
//       （2）索引为i的节点的左子节点为2i，右子节点为2i + 1，当然他们得 < size
//     4、证明思路就是假设父节点层数为h，子节点层数为h+1，假定层数从0编号，父节点位于当前层的第n个节点，求出父节点和子节点的表达式，再进行比较
//     5、索引1开始的情况，左子节点索引是父节点索引的两倍，换成索引0开始，就可以想象i => i-1, 2i => 2i-1, 2i+1 => 2i+1-1，然后把i-1看成整体视作索引0开始下对应的索引

/**
 * 基于大顶堆来实现优先级队列，根节点就是优先级最高的
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/3 16:07
 */
public class PriorityQueue3<E extends Priority> implements Queue<E>, Iterable<Integer> {
    private Priority[] arr; // 用于存放堆节点的数组，堆又是基于完全二叉树，堆的节点要实现Priority，用多态，里面实际会存放的不是Priority而是其实现类，每创建一个优先级队列实例时，E是唯一指定的某个实现类
    private int size; // 数组的大小，指向尾元素的下一个元素，默认0

    /**
     * 用构造方法初始化
     *
     * @param capacity 容量
     */
    public PriorityQueue3(int capacity) {
        arr = new Priority[capacity];
    }

    /**
     * 入队 log(n)
     *
     * @param value 待插入值
     * @return 入队成功返回true
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        insert(value);
        return true;
    }

    /**
     * 出队并删除 log(n)
     *
     * @return 出队的元素
     */
    @SuppressWarnings("all")
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        // 1、交换根节点和最后一层从左往右最后一个节点
        swap(0, size - 1);
        // 2、删除最后一层从左往右最后一个节点
        E value = (E) arr[--size];
        arr[size] = null;
        // 3、根节点下潜到合理位置
        down(0);
        return value;
    }

    /**
     * 获取优先级最高的元素
     *
     * @return 优先级最高的元素
     */
    @SuppressWarnings("all")
    @Override
    public E peek() {
        return (E) arr[0];
    }

    /**
     * 判断是否为空
     *
     * @return 空返回true
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * 迭代器，遍历时获取优先级
     *
     * @return 迭代器
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;

            @Override
            public boolean hasNext() {
                return index != size;
            }

            @Override
            public Integer next() {
                return arr[index++].priority();
            }
        };
    }

    /**
     * 往表示大顶堆的数组里面插入元素
     *
     * @param value 待插入元素
     */
    private void insert(E value) {
        int child = size++; // 子节点索引
        int parent = (child - 1) >> 1; // 父节点索引
        // 让小于插入元素的优先级的元素下潜
        while (child > 0 && arr[parent].priority() < value.priority()) {
            arr[child] = arr[parent];
            child = parent;
            parent = (child - 1) >> 1;
        }
        // 将待插入元素插入到空出来的位置
        arr[child] = value;
    }

    /**
     * 交换两个索引处的节点
     *
     * @param index1 索引1
     * @param index2 索引2
     */
    private void swap(int index1, int index2) {
        Priority temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    /**
     * 节点下潜
     *
     * @param root 指定节点节点，通常都是从根节点开始下潜
     */
    private void down(int root) {
        // 递的时候找出父节点，左子节点，右子节点中优先级最大的一个节点
        int left = root * 2 + 1;
        int right = left + 1;
        int max = max(root, left, right);
        if (max == root) { // 如果是父节点，则为终止条件
            return;
        }
        // 如果是子节点，则交换
        swap(root,max);
        down(max);
        // 归的时候啥也不干
    }

    /**
     * 求出父节点、左子节点、右子节点中最大优先级的节点在数组的索引
     *
     * @param root  父节点在数组中的索引
     * @param left  左子节点在数组中的索引
     * @param right 右子节点在数组中的索引
     * @return 最大优先级的节点在数组中的索引
     */
    private int max(int root, int left, int right) {
        // 算出的左子节点索引不在数组范围内，说明不存在左子节点，那么右子节点也不会存在，最大的就是root
        if (left >= size) {
            return root;
        }
        // 右子节点等于size，说明左子节点是最后一层从左往右最后一个节点，则比较root和left
        if (right == size) {
            return arr[root].priority() > arr[left].priority() ? root : left;
        }
        // left和right节点都存在
        if (arr[root].priority() >= arr[left].priority()) {
            return arr[root].priority() >= arr[right].priority() ? root : right;
        }
        return arr[left].priority() >= arr[right].priority() ? left : right;
    }

    /**
     * 扩容
     * @param capacity 容量
     */
    public void expansion(int capacity){
        if (capacity <= arr.length) {
            throw new IllegalArgumentException("参数 <" + capacity + "> 不能比" + arr.length + "小");
        }
        Priority[] array = new Priority[capacity];
        System.arraycopy(arr,0,array,0,size);
        arr = array;
    }
}
